3869. Метеонаблюдения

Алексей учится в пятом классе и собирается стать метеорологом. Недавно он завел дневник, в который занес ежедневные измерения температуры в родном городе. Алексей нашел архивные данные за последние несколько сотен лет, а это означает, что данных у него очень и очень много. Программировать он не умеет и просит Вас написать программу, которая вычисляет среднюю температуру за k последовательных дней, причем такие значения ему нужны за весь период наблюдений:

· Средняя температура с 1 по k-ый день

· Средняя температура со 2 по (k + 1) -ый день

· И так далее, пока есть данные.

А после этого из всех вычисленных значений Алексею нужны только два числа – минимальные и максимальные значения. Помогите Алексею и напишите для него эту программу.

Вход. В первой строке содержатся два целых числа n и k – количество измерений температуры и количество дней для вычисления средней температуры (1 ≤ k ≤ n ≤ 10⁵). В следующей строке содержится n целых чисел – данные измерений температуры. Каждое из этих чисел находится в интервале (-100, 100).

Выход. Вывести две строки, которые содержат минимальную и максимальную среднюю температуру, вычисленную на отрезках длины k. Число округлите до ближайшего целого.

Пример входа	Пример выхода
4 2 10 12 18 16	11 17

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть t₁, t₂, …, t_n – наблюдаемые температуры. Вычислим частичные суммы температур в массиве sum. То есть положим sum[i] = t₁ + t₂ +… + t_i (1 ≤ i ≤ n). Для этого воспользуемся рекуррентностью: sum[0] = 0, sum[i] = sum[i – 1] + t_i.

Средняя температура с (i – k + 1)-го по i-ый день (протяженность интервала k дней) составляет (t_{i – k + 1} +… + t_i) / k = (sum[i] – sum[i – k]) / k. Однако для простоты будем искать минимальное и максимальное значение суммы температур на всех промежутках длины k (потом при выводе средней температуры эти значения сумм разделим на k). То есть вычисляем:

· min =

· max =

Тогда искомая минимальная и максимальная средняя температура на отрезках длины k соответственно равны min / k и max / k.

Реализация алгоритма

Объявим массив частичных сумм sum и константу бесконечность INF.

#define MAX 100010

#define INF 2000000000

int sum[MAX];

Читаем входные данные.

scanf("%d %d",&n,&k);

Вычисляем частичные суммы измерений температур.

sum[0] = 0;

for(i = 1; i <= n; i++)

{

scanf("%d",&val);

sum[i] = sum[i - 1] + val;

}

Находим минимальное и максимальное значение среди всех сумм с k слагаемыми.

min = INF; max = -INF;

for(i = k; i <= n; i++)

{

if (sum[i] - sum[i - k] < min) min = sum[i] - sum[i - k];

if (sum[i] - sum[i - k] > max) max = sum[i] - sum[i - k];

}

Выводим ответ.

printf("%.0lf\n%.0lf\n",1.0*min/k,1.0*max/k);